/* 已知一棵树的层次序列和每个节点的度，编写算法构造此树的孩子兄弟链表 */
#include <iostream>
#include "CBNode.h"
#include "BiTreefun.h"
using namespace std;

// 创建二叉树
void create(CBNode *&T, char e[], int degree[], int n)
{
  // 存储二叉树的结点
  CBNode *p = new CBNode[maxsize]; 
  
  // 为结点赋值
  int i, j, d, k = 0;
  for (i = 0; i < n; ++i)
  {
    p[i].data = e[i];
    p[i].lchild = NULL;
    p[i].rchild = NULL;
  }
  
  // 遍历各个结点
  for (i = 0; i < n; ++i)
  {
    // 获取结点的度
    d = degree[i];

    // 如果度不为0
    if (d)
    {
      // 链接孩子结点
      p[i].lchild = &p[++k];
      
      // 链接兄弟结点
      for (j = 2; j <= d; ++j)
      {
        ++k;
        p[k - 1].rchild = &p[k];
      }
    }
  }
  T = p;
}

// 前序遍历
void pre(CBNode *T)
{
  if (T != NULL)
  {
    cout << T->data << " ";
    pre(T->lchild);
    pre(T->rchild);
  }
}

int main()
{
  // 7个结点的数值
  char e[7] = "123456";
  
  // 每个结点的度
  int degree[6] = {3, 0, 2, 0, 0, 0};
  
  // 创建二叉树
  CBNode *T;
  create(T, e, degree, 6);
  
  // 层次遍历
  for (int i = 0; i < 6; ++i)
    cout << T[i].data << endl;
  
  // 先序遍历
  pre(T);
  return 0;
}
